/*
Revision History:
Author                          Date          Version     Description of Changes
------------------------------------------------------------------------------------------
Jongwon Seo				 	 2010/02/20 	    1.0				 Created
neryong@gmail.com
*/

#ifndef __IP_TRIE_H__
#define __IP_TRIE_H__

#ifdef LINUX
#include <arpa/inet.h>
#else
#include <winsock2.h>
#endif
#include <bit_trie.h>

namespace neryong
{

template<class T,class DATA>
class base_ipv4_trie : public T
{
public:
	enum
	{
		bit_count_of_ip = sizeof(uint32_t)*8,
	};
	inline	void	insert_by_mask(uint32_t ip,uint32_t mask_len,const DATA& data)
	{
		ip = htonl(ip);
		T::insert((uint8_t*)&ip,mask_len,data);
	}
	inline	void	insert_by_count(uint32_t ip,uint32_t count,const DATA& data)
	{
		uint32_t this_count;
		while ( count )
		{
			int fsb = find_first_set_bit(ip);
			if ( fsb == bit_count_of_ip )
				this_count = count;
			else
			{	this_count = 1<<fsb;
				this_count = (count>this_count)?this_count:count;
			}
			
			int lsb = find_last_set_bit(this_count);
			this_count = 1<<lsb;
			
			insert_by_mask(ip,bit_count_of_ip-lsb,data);
			ip += this_count;
			count -= this_count;
		}
	}
	inline	void	erase_by_mask(uint32_t ip,uint32_t mask_len,const DATA& data)
	{
		ip = htonl(ip);
		erase((uint8_t*)&ip,mask_len,data);
	}
	inline	void	erase_by_count(uint32_t ip,uint32_t count,const DATA& data)
	{
		uint32_t this_count;
		while ( count )
		{
			int fsb = find_first_set_bit(ip);
			if ( fsb == bit_count_of_ip )
				this_count = count;
			else
			{	this_count = 1<<fsb;
				this_count = (count>this_count)?this_count:count;
			}
			
			int lsb = find_last_set_bit(this_count);
			this_count = 1<<lsb;
			
			erase_by_mask(ip,bit_count_of_ip-lsb,data);
			ip += this_count;
			count -= this_count;
		}
	}
protected:
	/**
		\brief	if ip == 0x111 then returns 0, if ip == 0x110 then returns 1
	*/
	static inline	int		find_first_set_bit(uint32_t ip)
	{	int i;
		uint32_t m = 1;
		for ( i = 0 ; i < bit_count_of_ip ; i++ )
		{	if ( (ip & m) )
				break;
			m<<=1;
		}
		return i;
	}
	/**
		\brief	if ip == 0x111 then returns 2, if ip == 0x011 then returns 1
	*/
	static inline	int		find_last_set_bit(uint32_t ip)
	{	int i;
		uint32_t m = 1<<(bit_count_of_ip-1);
		for ( i = bit_count_of_ip-1 ; i >= 0 ; i-- )
		{	if ( (ip & m) )
				break;
			m>>=1;
		}
		return i;
	}
};

template<class DATA,class STRIDE_UTIL,class ALLOCATOR=std::allocator<char> >
class ipv4_trie : public  base_ipv4_trie<bit_trie<4,DATA,STRIDE_UTIL,ALLOCATOR >,DATA >
{
public:
	inline	const DATA*	find(uint32_t ip) const
	{
		ip = htonl(ip);
		return base_ipv4_trie<bit_trie<4,DATA,STRIDE_UTIL,ALLOCATOR >,DATA >::find((uint8_t*)&ip);
	}
};
	

template<class DATA,class STRIDE_UTIL,class ALLOCATOR=std::allocator<char> >
class ipv4_multi_trie : public  base_ipv4_trie<multi_bit_trie<4,DATA,STRIDE_UTIL,ALLOCATOR >,DATA >
{
public:
	template<class RESULT>
	inline	void	find(uint32_t ip,RESULT& r) const
	{
		ip = htonl(ip);
		base_ipv4_trie<multi_bit_trie<4,DATA,STRIDE_UTIL,ALLOCATOR >,DATA >::find((uint8_t*)&ip,r);
	}
};

}

#endif //__IP_TRIE_H__
